Exercise 7 (Homework 4).
(membership problem,
context-free languages,
CKY algorithm,
decidable properties)
Membership in a context-free language is decidable in polynomial time
Consider the following decision problem:
\mathtt{Membership_{CFL}}: \text{ given an input $x\in \{0,1\}^*$ and a context-free grammar $G$, determine whether } x\in L(G).
Show that \mathtt{Membership_{CFL}} can be decided in polynomial time w.r.t. |x| and the size of G. Do this describing how the Cocke-Kasami-Younger algorithm (CKY) works.
Caution
The CKY algorithm assumes as input a grammar in Chomsky normal form.